package gold.digger;

import gold.utils.InputUtil;
import org.apache.commons.lang.StringUtils;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC745 {
    public long startExecuteTime = System.currentTimeMillis();


    class WordFilter {
        Trie trie;
        String weightKey;

        public WordFilter(String[] words) {
            trie = new Trie();
            weightKey = "##";
            for (int i = 0; i < words.length; i++) {
                String word = words[i];
                Trie cur = trie;
                int m = word.length();
                for (int j = 0; j < m; j++) {
                    Trie tmp = cur;
                    for (int k = j; k < m; k++) {
                        String key = new StringBuilder().append(word.charAt(k)).append('#').toString();
                        if (!tmp.children.containsKey(key)) {
                            tmp.children.put(key, new Trie());
                        }
                        tmp = tmp.children.get(key);
                        tmp.weight.put(weightKey, i);
                    }
                    tmp = cur;
                    for (int k = j; k < m; k++) {
                        String key = new StringBuilder().append('#').append(word.charAt(m - k - 1)).toString();
                        if (!tmp.children.containsKey(key)) {
                            tmp.children.put(key, new Trie());
                        }
                        tmp = tmp.children.get(key);
                        tmp.weight.put(weightKey, i);
                    }
                    String key = new StringBuilder().append(word.charAt(j)).append(word.charAt(m - j - 1)).toString();
                    if (!cur.children.containsKey(key)) {
                        cur.children.put(key, new Trie());
                    }
                    cur = cur.children.get(key);
                    cur.weight.put(weightKey, i);
                }
            }
        }

        public int f(String pref, String suff) {
            Trie cur = trie;
            int m = Math.max(pref.length(), suff.length());
            for (int i = 0; i < m; i++) {
                char c1 = i < pref.length() ? pref.charAt(i) : '#';
                char c2 = i < suff.length() ? suff.charAt(suff.length() - 1 - i) : '#';
                String key = new StringBuilder().append(c1).append(c2).toString();
                if (!cur.children.containsKey(key)) {
                    return -1;
                }
                cur = cur.children.get(key);
            }
            return cur.weight.get(weightKey);
        }
    }

    class Trie {
        Map<String, Trie> children;
        Map<String, Integer> weight;

        public Trie() {
            children = new HashMap<String, Trie>();
            weight = new HashMap<String, Integer>();
        }
    }


    class WordFilter_Time_Exceed_Shit {
        String[] ss;

        public WordFilter_Time_Exceed_Shit(String[] words) {
            ss = words;
        }

        public int f(String a, String b) {
            int n = a.length(), m = b.length();
            for (int k = ss.length - 1; k >= 0; k--) {
                String cur = ss[k];
                int len = cur.length();
                if (len < n || len < m) continue;
                boolean ok = true;
                for (int i = 0; i < n && ok; i++) {
                    if (cur.charAt(i) != a.charAt(i)) ok = false;
                }
                for (int i = 0; i < m && ok; i++) {
                    if (cur.charAt(len - 1 - i) != b.charAt(m - 1 - i)) ok = false;
                }
                if (ok) return k;
            }
            return -1;
        }
    }


    class WordFilter_WA_Hard_To_Debug {

        public class Trie {

            public class Node {
                boolean isWord;
                Node[] children;
                HashSet<Integer> idxSet = new HashSet<>();

                public Node(boolean isWord) {
                    this.isWord = isWord;
                    children = new Node[26];
                }
            }

            private Node root;

            public Trie() {
                this.root = new Node(false);
            }

            public void insert(String word, int pos) {
                Node node = root;
                for (char c : word.toCharArray()) {
                    int idx = c - 'a';
                    if (node.children[idx] == null) {
                        node.children[idx] = new Node(false);
                    }
                    node = node.children[idx];
                }

                node.isWord = true;
                node.idxSet.add(pos);
            }

            Map<Node, HashSet<Integer>> memo = new HashMap<>();

            public HashSet<Integer> searchMaxMatchPrefix(String prefix) {
                Node node = root;
                for (char c : prefix.toCharArray()) {
                    int idx = c - 'a';
                    if (node.children[idx] == null) return new HashSet<>();
                    node = node.children[idx];
                }

                // 当前node 是初始搜索根结点
                if (memo.containsKey(node)) return memo.get(node);
                HashSet<Integer> ansSet = dfsSearchMaxPos(node);
                memo.put(node, ansSet);
                return ansSet;
            }

            private HashSet<Integer> dfsSearchMaxPos(Node root) {
                if (null == root) return new HashSet<>();
                HashSet<Integer> ans = new HashSet<>(root.idxSet);
                for (int i = 0; i < 26; i++) {
                    HashSet<Integer> nextAns = dfsSearchMaxPos(root.children[i]);
                    ans.addAll(nextAns);
                }

                return ans;
            }
        }

        public Trie prefixTree = new Trie(), suffixTree = new Trie();

        public WordFilter_WA_Hard_To_Debug(String[] words) {
            for (int i = 0; i < words.length; i++) {
                prefixTree.insert(words[i], i);
                suffixTree.insert(new StringBuilder(words[i]).reverse().toString(), i);
            }
        }

        Map<String, Integer> matchMemo = new HashMap<>();

        public int f(String pref, String suff) {
            String curKey = pref + "_" + suff;
            if (matchMemo.containsKey(curKey)) return matchMemo.get(curKey);

            HashSet<Integer> prefPosSet = prefixTree.searchMaxMatchPrefix(pref);
            HashSet<Integer> suffPosSet = suffixTree.searchMaxMatchPrefix(new StringBuilder(suff).reverse().toString());
            prefPosSet.retainAll(suffPosSet);
            int finalPos = prefPosSet.isEmpty() ? -1 : new TreeSet<>(prefPosSet).last();
            matchMemo.put(curKey, finalPos);
            return finalPos;
        }
    }

    public void run() {
//        WordFilter wordFilter = new WordFilter(new String[]{"apple"});
//        System.out.println(wordFilter.f("a", "e"));

//        WordFilter wordFilter = new WordFilter(new String[]{"abbba", "abba"});
//        System.out.println(wordFilter.f("ab", "ba"));


        List<String> lineList = loadLineList("/Users/zhfan/Downloads/input_case.txt");
        String[] inputList = new String[lineList.size()];
        for (int i = 0; i < lineList.size(); i++) inputList[i] = lineList.get(i);
        WordFilter wordFilter = new WordFilter(inputList);

        List<String> testCaseList = loadLineList("/Users/zhfan/Downloads/input_result.txt");
        for (String testCaseStr : testCaseList) {
            System.out.println(wordFilter.f(testCaseStr.split(",")[0], testCaseStr.split(",")[1]));
        }
    }

    public static List<String> loadLineList(String fileName) {
        BufferedReader br = null;
        String line = "";
        List<String> candidateList = new ArrayList<>();

        try {
            br = new BufferedReader(new FileReader(fileName));
            while ((line = br.readLine()) != null) {
                if (StringUtils.isBlank(line)) continue;
                candidateList.add(line);
            }
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            if (br != null) {
                try {
                    br.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }

        return candidateList;
    }

    public static void main(String[] args) throws Exception {
        LC745 an = new LC745();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
